package leetcode.BinarySearch;

public class MyPow {

    public static double myPow(double x, int n) {

        double result = pow(x, n);
        if (n < 0) {
            result = 1 / result;
        }
        return result;
    }

    private static double pow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double half;
        if ((n & 1) == 1) {
            half = pow(x, n / 2);
            return x * half * half;
        } else {
            double half2 = pow(x, n / 2);
            return half2 * half2;
        }
    }

    public static double myPow1(double x, int n) {
        if (x == 1.0) {
            return 1.0;
        }

        double result = 0.0;
        if (n == 0) {
            return 1.0;
        } else if (n > 0) {
            if (n == 1) {
                return x;
            } else {
                int n1 = n / 2;
                int n2 = n - n1;
                result = myPow1(x, n1);
                result = result * result;
                if (n1 != n2) {
                    result = result * x;
                }
                return result;
            }
        } else if (n < 0) {
            if (n == Integer.MIN_VALUE) {
                result = 1 / (x * myPow1(x, -(n + 1)));
            } else {
                result = 1 / myPow1(x, -n);
            }
            return result;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(myPow1(2, 9));
    }
}
